package ljl.alg.wangzheng_camp.round1.bisection;

public class _69_sqrt {
    
    /**
     * 又错啦！
     *
     * 看来二分法是要重点学习的重中之重
     * */
    public int mySqrt2(int x) {
        int l = 0, r = x;
        while (l < r) {
            // 他妈的这个 +1 是怎么回事啊，我都没注意！
            int mid = (l + r + 1) >>> 1;
            long mul = (long) mid * mid;
            if (mul > Integer.MAX_VALUE) {
                r = mid - 1;
                continue;
            }
            if (mul <= x) l = mid;
            else r = mid - 1;
        }
        return l;
    }
    
    public int mySqrt1(int x) {
        int l = 0, r = x;
        while (l < r) {
            int mid = (l + r + 1) >>> 1;
            if ((long)mid * mid > x) r = mid - 1;
            else l = mid;
        }
        return l;
    }
    
    /**
     * 我觉磨着还行啊
     * */
    public int mySqrt(int x) {
        int l = 0, r = x, res = 0;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            if ((long) mid * mid > x) r = mid - 1;
            else {
                res = mid;
                l = mid + 1;
            }
        }
        return res;
    }
    
    /**
     * 怎么可以没有牛顿迭代
     *
     * c 是要求平方根的数
     * y = x2 - c
     * 然后呢，斜率是 2x，假设和 x 轴交点为 x1, y1，则连线的方程为
     * y1 - (x2 - c)) / (x1 - x) = 2x
     * 也就是 y1 = 2x(x1 - x) + x2 - c
     *
     * 然后 y1 这个变量没啥用，想推的是 x 和 x1 的关系，因为要找使 y 为 0 的点
     * 所以带入 y = x2 - c
     *
     * x1^2 - c = 2x^2 -2xx1 + x2 - c 然后求不出来了
     * 而且前面 x1 - x 写成 x - x1 了，不过没事，反正思路错了，结果对不了
     *
     * 其实不对，不应该带入 y1 和 x1 关系，应该直接令 y1 为 0，则
     *
     * 2x^2 - 2xx1 = x2 - c
     * x1 = (x^2 - c) / 2x = (x - c/x) / 2
     *
     * 就得到 x1 = (x - c/x) / 2 了
     * 这就是递推公式
     *
     * 不停的拿新得到的 x 带入右边那个公式，不断地逼近真实结果
     * c 一开始值为要求平方发的那个值
     *
     *
     * */
    public int mySqrt_newton(int x) {
        if (x == 0) {
            return 0;
        }
        double x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + x / x0);
            int xx = (int) xi;
            if ((long)xx * xx <= x) return xx;
            x0 = xi;
        }
    }
    
    /**
     * 不要被 fuck 分心
     * */
    public int mySqrtfuck(int x) {
        long fuck = x;
        while (fuck * fuck > x) fuck = (fuck + x / fuck) / 2;
        return (int) fuck;
    }
}
